Kruskal's alogrithm

Kruskal 又稱K氏法，是將各邊依權值大小由小到大排列，接著從權值最低的邊線開始架構最小成本擴張樹，如果加入的邊線會造成迴路則捨棄不用，直到加入了n-1個邊線為止。

最小成本擴張樹:

⓵ 把所有邊線的成本列出由小到大排序:

⓶ 選擇成本最低的一條邊線作為架構最小成本擴張樹的起點。

⓷ 依步驟1所建立的表格，依序加入邊線。

⓸ C-D加入會形成迴路，所以直接跳過。

完成

Kruskal演算法通常使用一個稱為「Union-Find」的數據結構來檢查是否將邊添加到MST中會形成迴路，它具有查找(Find)和聯合(Union)。

fn kruskal(edges: &mut Vec<Edge>, num_vertices: usize) -> Vec<Edge> {
    edges.sort(); 
    // 將邊按照權重排序
    let mut mst = Vec::new(); 
    // 最小生成樹的邊集合
    let mut uf = UnionFind::new(num_vertices); 
    // 用於檢查是否形成環路的 Union-Find 結構

    for edge in edges {
        if !uf.connected(edge.from, edge.to) {
            // 如果不會形成環路，則將這條邊添加到 MST 中
            uf.union(edge.from, edge.to);
            mst.push(*edge);
        }
    }

    mst
}

edges是一個可變的Edge向量，代表所有的邊。函數使用迴圈遍歷edges中的每條邊，並對每一條邊進行處理。

Prim's Algorithm

普林演算法是一種找到最小生成樹(MST)的演算法，主要是逐步擴展MST，從初始節點開始，每次選擇一個最小權重的邊來連接MST中的節點和不在MST中的節點，直到所有點都包含在MST中為止。

演算法步驟:

① 初始化一個空的MST。

② 選擇一個初始節點，將其添加到MST中。

③ 重複以下步驟，直到MST包含所有節點:

Ⅰ.找到MST中的節點和不在MST中的節點之間的最小權重的邊。

Ⅱ.將該邊添加到MST中，並將新節點添加到MST中。

最小生成樹:

⓵ 從每棵樹中挑出最小的邊

(1,6)、(2,7)、(3,4)、(5,4)

⓶ 再從中挑出最小的邊
(6,5)、(2,3)

③ 最後只剩一棵樹完成

Prim's演算法:

impl Graph {
    fn new(num_vertices: usize) -> Self {
        Graph {
            num_vertices,
            adjacency_list: vec![Vec::new(); num_vertices],
        }
    }

    fn add_edge(&mut self, from: usize, to: usize, weight: usize) {
        self.adjacency_list[from].push((to, weight));
        self.adjacency_list[to].push((from, weight)); // For undirected graph
    }
    // 添加邊，起始點from和終點to

    fn prim(&self) -> Vec<Edge> {
        let mut mst = Vec::new(); // Minimum Spanning Tree
        let mut visited = HashSet::new();
        let mut min_heap = BinaryHeap::new(); // Min-heap for edges


        visited.insert(0);

        for &(to, weight) in &self.adjacency_list[0] {
            min_heap.push(Edge {
                from: 0,
                to,
                weight,
            });
        }

        while let Some(edge) = min_heap.pop() {
            if !visited.contains(&edge.to) {
                visited.insert(edge.to);
                mst.push(edge.clone());

                for &(to, weight) in &self.adjacency_list[edge.to] {
                    if !visited.contains(&to) {
                        min_heap.push(Edge { from: edge.to, to, weight });
                    }
                }
            }
        }

        mst
    }
}

這邊應該不會太難吧☕☕！！

要是哪裡理解上還是邏輯上有錯請各位大大指正，感謝 🧙🧙🧙。